package com.czk.tree.huffmantree.practice.code;

import java.util.*;

/**
 * @Author:ChenZhangKun
 * @Date: 2021/6/28 18:58
 */
public class HuffmanCode {
    static StringBuilder builder = new StringBuilder();
    static Map<Byte, String> huffmanCodes = new HashMap<>(16);

    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        // 拿到bytes
        byte[] bytes = content.getBytes();
        System.out.println("content的byte长度为=" + bytes.length);
        // 创建对应的·list集合
        List<Node> nodes = getNodes(bytes);
        // 创建huffmantree
        Node huffmanTree = createHuffmanTree(nodes);
        // huffmanTree.preOrder();
        Map<Byte, String> codes = getCodes(huffmanTree, "", builder);
        // System.out.println(codes);
        byte[] zip = zip(bytes, codes);
        System.out.println(Arrays.toString(zip));
        byte[] decode = decode(codes, zip);
        System.out.println(Arrays.toString(decode));
        System.out.println(new String(decode));
    }
    public static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        StringBuilder builder=new StringBuilder();
        // 将buye数组转为二进制得字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            // 判断是否是最后一个字节
            boolean flag=(i==huffmanBytes.length-1);
            builder.append(byteToBitString(!flag,huffmanBytes[i]));
        }
        Map<String,Byte> map=new HashMap<>();
        // 翻转huffman编码
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(),entry.getKey());
        }
        // 创建集合，存储list
        List<Byte> list=new ArrayList<>();
        for (int i = 0; i < builder.length();) {
            int count=1; // 晓得计数器
            boolean flag=true;
            Byte b=null;
            while (flag){
                // 截取
                String substring = builder.substring(i, i + count);
                b = map.get(substring);
                if (b==null){
                    count++;
                }else {
                    flag=false;
                }
            }
            list.add(b);
            i+=count;
        }
        // 得到原来的byte数组
        byte[] b=new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i]=list.get(i);
        }
        return b;
    }
    /**
     *
     * @param flag 是否需要补高位
     * @param b 传入的byte
     * @return
     */
    public static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        // 需要补高位
        if (flag) {
            // 正数需要
            temp |= 256;
        }
        // 转为二进制字符串
        String string = Integer.toBinaryString(temp);
        if (flag) {
            return string.substring(string.length()-8);
        }
        return string;
    }

    /**
     * @param bytes        原始字符串对应的byte
     * @param huffmanCodes 生成的哈夫曼编码map
     * @return
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        // 利用huffmancode将byte转成huffman对应的字符串
        StringBuilder builder = new StringBuilder();
        for (byte b : bytes) {
            builder.append(huffmanCodes.get(b));
        }
        String string = builder.toString();
        // 定义步长
        int len;
        if (builder.length() % 8 == 0) {
            len = builder.length() / 8;
        } else {
            len = builder.length() / 8 + 1;
        }
        byte[] huffmanCodeBytes = new byte[len];
        // 定义第几个byte
        int index = 0;
        for (int i = 0; i < builder.length(); i += 8) {
            String strByte;
            if (i + 8 > builder.length()) {
                strByte = builder.substring(i);
            } else {
                strByte = builder.substring(i, i + 8);
            }
            // 转为byte
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;

        }
        return huffmanCodeBytes;
    }

    /**
     * 生成对应的哈夫曼编码
     *
     * @param node
     * @param code
     * @param builder
     * @return
     */
    public static Map<Byte, String> getCodes(Node node, String code, StringBuilder builder) {
        StringBuilder builder2 = new StringBuilder(builder);
        // 将code加入builder
        builder2.append(code);
        if (node != null) {
            // 叶子节点还是非叶子节点
            if (node.data == null) {
                // 递归
                getCodes(node.left, "0", builder2);
                // 向右递归
                getCodes(node.right, "1", builder2);
            } else {
                // 叶子节点
                huffmanCodes.put(node.data, builder2.toString());
            }
        }
        return huffmanCodes;
    }

    /**
     * 构建huffmanTree
     *
     * @param list
     * @return
     */
    public static Node createHuffmanTree(List<Node> list) {
        while (list.size() > 1) {
            Collections.sort(list);
            Node left = list.get(0);
            Node right = list.get(1);
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        return list.get(0);
    }

    /**
     * 创建node集合
     *
     * @param bytes
     * @return
     */
    public static List<Node> getNodes(byte[] bytes) {
        // 创建集合
        List<Node> nodeList = new ArrayList<>(10);
        Map<Byte, Integer> map = new HashMap<>(16);
        // 通缉byte出现的次数
        for (byte aByte : bytes) {
            if (map.containsKey(aByte)) {
                Integer integer = map.get(aByte);
                map.put(aByte, ++integer);
            } else {
                map.put(aByte, 1);
            }
        }
        // 遍历map
        Set<Map.Entry<Byte, Integer>> entries = map.entrySet();
        for (Map.Entry<Byte, Integer> entry : entries) {
            Byte key = entry.getKey();
            Integer value = entry.getValue();
            Node node = new Node(key, value);
            nodeList.add(node);
        }
        return nodeList;
    }
}

class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }
}
